package stack.medium;

import java.util.Stack;

/**
 * 反转每对括号间的子串
 * 示例 1：
 *
 * 输入：s = "(abcd)"
 * 输出："dcba"
 * 示例 2：
 *
 * 输入：s = "(u(love)i)"
 * 输出："iloveu"
 * 解释：先反转子字符串 "love" ，然后反转整个字符串。
 * 示例 3：
 *
 * 输入：s = "(ed(et(oc))el)"
 * 输出："leetcode"
 * 解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。
 * 示例 4：
 *
 * 输入：s = "a(bcdefghijkl(mno)p)q"
 * 输出："apmnolkjihgfedcbq"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses
 */
public class ReverseSubstringsBetweenEachPairOfParentheses_1190 {

    public String reverseParentheses(String s) {
        Stack<String> stack = new Stack<>();
        int i = 0;
        while (i < s.length()) {
            if (stack.isEmpty() && s.charAt(i) != '(') {
                stack.push(String.valueOf(s.charAt(i)));
            } else if (s.charAt(i) == '(') {
                stack.push(String.valueOf('('));
            } else if (s.charAt(i) == ')') {
                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty() && !stack.peek().equals(String.valueOf('('))) {
                    sb.append(stack.pop());
                }
                stack.pop();
                stack.push(sb.reverse().toString());
            } else {
                stack.push(String.valueOf(s.charAt(i)));
            }
            i++;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        ReverseSubstringsBetweenEachPairOfParentheses_1190 rs = new ReverseSubstringsBetweenEachPairOfParentheses_1190();
        System.out.println(rs.reverseParentheses("a(bcdefghijkl(mno)p)q"));
    }
}
